{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Greatest Sum Divisible by Three"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #dynamic-programming #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #动态规划 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxSumDivThree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #可被三整除的最大和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组&nbsp;<code>nums</code>，请你找出并返回能被三整除的元素最大和。</p>\n",
    "\n",
    "<ol>\n",
    "</ol>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [3,6,5,1,8]\n",
    "<strong>输出：</strong>18\n",
    "<strong>解释：</strong>选出数字 3, 6, 1 和 8，它们的和是 18（可被 3 整除的最大和）。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [4]\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>4 不能被 3 整除，所以无法选出数字，返回 0。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [1,2,3,4,4]\n",
    "<strong>输出：</strong>12\n",
    "<strong>解释：</strong>选出数字 1, 3, 4 以及 4，它们的和是 12（可被 3 整除的最大和）。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 4 * 10^4</code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10^4</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [greatest-sum-divisible-by-three](https://leetcode.cn/problems/greatest-sum-divisible-by-three/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [greatest-sum-divisible-by-three](https://leetcode.cn/problems/greatest-sum-divisible-by-three/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,6,5,1,8]', '[4]', '[1,2,3,4,4]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumDivThree(self, nums: List[int]) -> int:\n",
    "        s1, s2, s3 = 0, 0, 0\n",
    "        for num in nums:\n",
    "            ts = [s1 + num, s2 + num, s3 + num]\n",
    "            for t in ts:\n",
    "                r = t % 3\n",
    "                if r == 0:\n",
    "                    s3 = max(s3, t)\n",
    "                elif r == 1:\n",
    "                    s1 = max(s1, t)\n",
    "                else:\n",
    "                    s2 = max(s2, t)\n",
    "        return s3\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumDivThree(self, nums: List[int]) -> int:\n",
    "        f=[0,0,0]\n",
    "\n",
    "        for a in nums:\n",
    "            for i in f[:]:\n",
    "                f[(i+a)%3]=max(f[(i+a)%3],i+a)\n",
    "\n",
    "        return f[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumDivThree(self, nums: List[int]) -> int:\n",
    "        heap1 = [-inf,-inf]\n",
    "        heap2 = [-inf,-inf]\n",
    "        heapify(heap1)\n",
    "        heapify(heap2)\n",
    "        s = 0\n",
    "        for i in nums:\n",
    "            s+=i\n",
    "            if i%3==2 and i<-heap2[0]:\n",
    "                heapreplace(heap2,-i)\n",
    "            elif i%3==1 and i<-heap1[0]:\n",
    "                heapreplace(heap1,-i)\n",
    "        print(heap1)\n",
    "        print(heap2)\n",
    "        print(s)\n",
    "        if s%3==0:\n",
    "            return s\n",
    "        elif s%3==1:\n",
    "            return max(s+heap1[1],s+heap2[0]+heap2[1],0)\n",
    "        else:\n",
    "            return max(s+heap2[1],s+heap1[0]+heap1[1],0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumDivThree(self, nums: List[int]) -> int:\n",
    "        #思路一 找出数组中%3余2 与 余1的  建立三个数组\n",
    "        s = sum(nums)\n",
    "        if not s % 3:\n",
    "            return s\n",
    "        nums1 = []\n",
    "        nums2 = []        \n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] % 3 == 1:                \n",
    "                nums1.append(nums[i])\n",
    "            elif nums[i] % 3 == 2:\n",
    "                nums2.append(nums[i])\n",
    "        nums1.sort()\n",
    "        nums2.sort()    \n",
    "        if s % 3 == 2:\n",
    "            nums1, nums2 = nums2, nums1  #代码复用 若余数为2，则将num1变成2数组\n",
    "        ans = s - nums1[0] if nums1 else 0  # 余数为 1 时，可以减去一个余数为1的数\n",
    "        if len(nums2) > 1:  # 余数为 1 时，可以减去两个余数为2的数\n",
    "            ans = max(ans, s - nums2[0] -nums2[1]) #注意此处不能用ans代替s\n",
    "        return ans\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumDivThree(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        nums_copy = [i for i in nums]\n",
    "        nums_copy.sort()\n",
    "        nums_mod3 = [i for i in nums_copy]\n",
    "        for i in range(0, len(nums_mod3)):\n",
    "            nums_mod3[i] = nums_mod3[i] % 3\n",
    "            res = res + nums[i]\n",
    "        mod2_index = []\n",
    "        mod1_index = []\n",
    "\n",
    "        if res % 3 == 0:\n",
    "            return res\n",
    "        else:\n",
    "            for i in range(0, len(nums)):\n",
    "                if nums_mod3[i] == 2:\n",
    "                    mod2_index.append(i)\n",
    "                elif nums_mod3[i] == 1:\n",
    "                    mod1_index.append(i)\n",
    "\n",
    "                if res % 3 == 1:\n",
    "                    if len(mod1_index) >= 1 and len(mod2_index) >= 2:\n",
    "                        minus_with_mod2 = nums_copy[mod2_index[0]] + nums_copy[mod2_index[1]]\n",
    "                        minus_with_mod1 = nums_copy[mod1_index[0]]\n",
    "                        minus_val = minus_with_mod1 if minus_with_mod2 > minus_with_mod1 else minus_with_mod2\n",
    "                        return res - minus_val\n",
    "                else:\n",
    "                    if len(mod1_index) >= 2 and len(mod2_index) >= 1:\n",
    "                        minus_with_mod1 = nums_copy[mod1_index[0]] + nums_copy[mod1_index[1]]\n",
    "                        minus_with_mod2 = nums_copy[mod2_index[0]]\n",
    "                        minus_val = minus_with_mod1 if minus_with_mod2 > minus_with_mod1 else minus_with_mod2\n",
    "                        return res - minus_val\n",
    "\n",
    "            if res % 3 == 1:\n",
    "                if len(mod1_index) >= 1:\n",
    "                    minus_with_mod1 = nums_copy[mod1_index[0]]\n",
    "                    minus_val = minus_with_mod1\n",
    "                    return res - minus_val\n",
    "                elif len(mod2_index) >= 2:\n",
    "                    minus_with_mod2 = nums_copy[mod2_index[0]] + nums_copy[mod2_index[1]]\n",
    "                    minus_val = minus_with_mod2\n",
    "                    return res - minus_val\n",
    "            else:\n",
    "                if len(mod2_index) >= 1:\n",
    "                    minus_with_mod2 = nums_copy[mod2_index[0]]\n",
    "                    minus_val = minus_with_mod2\n",
    "                    return res - minus_val\n",
    "                elif len(mod1_index) >= 2:\n",
    "                    minus_with_mod1 = nums_copy[mod1_index[0]] + nums_copy[mod1_index[1]]\n",
    "                    minus_val = minus_with_mod1\n",
    "                    return res - minus_val\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumDivThree(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        # dp[r][ix] = max sum of the previous ix numbers  and mod 3 is r \n",
    "        dp = [[0] * n for ix in range(3)]\n",
    "        dp[nums[0]%3][0] = nums[0]\n",
    "        for ix in range(1,n):\n",
    "            r = nums[ix]%3\n",
    "            if r == 0:\n",
    "                dp[0][ix] = dp[0][ix-1] + nums[ix]\n",
    "                if dp[1][ix-1]>0:\n",
    "                    dp[1][ix] = dp[1][ix-1] + nums[ix]\n",
    "                if dp[2][ix-1]>0:\n",
    "                    dp[2][ix] = dp[2][ix-1] + nums[ix]\n",
    "            elif r == 1:\n",
    "                for l in range(3):\n",
    "                    dp[l][ix] = dp[l][ix-1]\n",
    "                if dp[2][ix-1] > 0:\n",
    "                    dp[0][ix] = max(dp[0][ix], dp[2][ix-1] + nums[ix])\n",
    "                dp[1][ix] = max(dp[1][ix-1], dp[0][ix-1]+nums[ix])\n",
    "                if dp[1][ix-1] > 0:\n",
    "                    dp[2][ix] = max(dp[2][ix-1], dp[1][ix-1]+nums[ix])\n",
    "            else:\n",
    "                # r = 2\n",
    "                for l in range(3):\n",
    "                    dp[l][ix] = dp[l][ix-1]\n",
    "                if dp[1][ix-1] > 0:\n",
    "                    dp[0][ix] = max(dp[0][ix-1], dp[1][ix-1]+nums[ix])\n",
    "                if dp[2][ix-1] > 0:\n",
    "                    dp[1][ix] = max(dp[1][ix-1], dp[2][ix-1]+nums[ix])\n",
    "                dp[2][ix] = max(dp[2][ix-1], dp[0][ix-1]+nums[ix])\n",
    "            # print(dp)\n",
    "        return dp[0][n-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumDivThree(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [[0,0,0] for _ in range(n+1)]\n",
    "        for i in range(n):\n",
    "            for j in range(3):\n",
    "                dp[i+1][j] = max(dp[i+1][j], dp[i][j])\n",
    "                dp[i+1][(dp[i][j]+nums[i])%3] = max(dp[i+1][(dp[i][j]+nums[i])%3], dp[i][j]+nums[i]) \n",
    "        # print(dp)\n",
    "        return dp[n][0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumDivThree(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [[-inf] * 3 for _ in range(n+1)]\n",
    "        dp[0][0] = 0\n",
    "        for i,x in enumerate(nums):\n",
    "            for j in range(3):\n",
    "                dp[i+1][j] = max(dp[i][j],dp[i][(j+x)%3] + x)\n",
    "        return dp[-1][0]\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumDivThree(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [[float('-inf')] * 3 for _ in range(n)]\n",
    "        dp[0][0] = 0\n",
    "        dp[0][nums[0] % 3] = nums[0]\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            for j in range(3):\n",
    "                k = (j - nums[i] % 3 + 3) % 3\n",
    "                dp[i][j] = max(dp[i - 1][j], dp[i - 1][k] + nums[i])\n",
    "        print(dp)\n",
    "        return dp[-1][0]\n",
    "\n",
    "        # n = len(nums)\n",
    "        # dp = [[float('-inf')] * 3 for _ in range(n + 1)]\n",
    "        # dp[0][0] = 0\n",
    "        \n",
    "        # for i in range(1, n + 1):\n",
    "        #     for j in range(3):\n",
    "        #         k = (j - nums[i - 1] % 3 + 3) % 3\n",
    "        #         dp[i][j] = max(dp[i - 1][j], dp[i - 1][k] + nums[i - 1])\n",
    "        # print(dp)\n",
    "        # return dp[-1][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumDivThree(self, nums: List[int]) -> int:\n",
    "\n",
    "        # dp[i][j] 表示前i个数选若干个，除以3余j的最大和\n",
    "\n",
    "        dp = [[0,0,0] for _ in range(len(nums))]\n",
    "        k = nums[0]%3\n",
    "        dp[0][k] = nums[0]\n",
    "\n",
    "        for i in range(1,len(nums)):\n",
    "            for j in range(3):\n",
    "                dp[i][j] = max(dp[i-1][j], dp[i-1][(j - nums[i]%3)%3] + nums[i] if ((dp[i-1][(j - nums[i]%3)%3] + nums[i])%3) == j else dp[i-1][j])\n",
    "                print(j,(j + 3 - nums[i]%3)%3, dp[i-1][j], dp[i-1][(j - nums[i]%3)%3] + nums[i])\n",
    "        print(dp)\n",
    "        return dp[-1][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumDivThree(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [[[-1] * 3 for _ in range(2)] for _ in range(n + 1)]\n",
    "        dp[0][0][0] = 0\n",
    "        for i in range(n):\n",
    "            num = nums[i]\n",
    "            dp[i + 1][0][0] = max(dp[i][0][0], dp[i][1][0])\n",
    "            if max(dp[i][0][1], dp[i][1][1]) >= 0:\n",
    "                dp[i + 1][0][1] = max(dp[i][0][1], dp[i][1][1])\n",
    "            if max(dp[i][0][2], dp[i][1][2]) >= 0:\n",
    "                dp[i + 1][0][2] = max(dp[i][0][2], dp[i][1][2])\n",
    "            dp[i + 1][1][num % 3] = max(dp[i][0][0], dp[i][1][0]) + num\n",
    "            if max(dp[i][0][1], dp[i][1][1]) >= 0:\n",
    "                dp[i + 1][1][(num + 1) % 3] = max(dp[i][0][1], dp[i][1][1]) + num\n",
    "            if max(dp[i][0][2], dp[i][1][2]) >= 0:\n",
    "                dp[i + 1][1][(num + 2) % 3] = max(dp[i][0][2], dp[i][1][2]) + num\n",
    "        return max(dp[n][0][0], dp[n][1][0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def maxSumDivThree(self, nums: List[int]) -> int:\n",
    "        dp=np.zeros((len(nums)+1,3))\n",
    "        dp[0][0]=0\n",
    "        dp[0][1]=float('-inf')\n",
    "        dp[0][2]=float('-inf')\n",
    "        for i in range(1,len(nums)+1):\n",
    "            if nums[i-1]%3==1:\n",
    "                dp[i][0]=max(dp[i-1][0],dp[i-1][2]+nums[i-1])\n",
    "                dp[i][1]=max(dp[i-1][1],dp[i-1][0]+nums[i-1]) \n",
    "                dp[i][2]=max(dp[i-1][2],dp[i-1][1]+nums[i-1])\n",
    "            if nums[i-1]%3==0:\n",
    "                dp[i][0]=max(dp[i-1][0],dp[i-1][0]+nums[i-1])\n",
    "                dp[i][1]=max(dp[i-1][1],dp[i-1][1]+nums[i-1])\n",
    "                dp[i][2]=max(dp[i-1][2],dp[i-1][2]+nums[i-1])\n",
    "            if nums[i-1]%3==2:\n",
    "                dp[i][0]=max(dp[i-1][0],dp[i-1][1]+nums[i-1])\n",
    "                dp[i][1]=max(dp[i-1][1],dp[i-1][2]+nums[i-1])\n",
    "                dp[i][2]=max(dp[i-1][2],dp[i-1][0]+nums[i-1])\n",
    "        return int(dp[len(nums)][0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "k = 3\n",
    "class Solution:\n",
    "    def maxSumDivThree(self, nums: List[int]) -> int:\n",
    "        # b = np.array([[1, 2], [3, 4]])\n",
    "        # n, dps = len(nums), [[-1_000_000_007]*k, [0]*k]\n",
    "        n, dps = len(nums), np.array([[-1_000_000_007]*k, [0]*k])\n",
    "        dps[0, 0] = 0\n",
    "\n",
    "        for i, num in enumerate(nums):\n",
    "            for j in range(k):\n",
    "                dps[i & 1 ^ 1, j] = max(dps[i & 1, j], dps[i & 1, (j + nums[i]) % k] + num)\n",
    "\n",
    "        return int(dps[n & 1, 0])\n",
    "        # print(int(dps[n & 1, 0]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy\n",
    "\n",
    "class Solution:\n",
    "    def maxSumDivThree(self, nums: List[int]) -> int:\n",
    "        dp = [[0 for _ in range(3)] for _ in range(len(nums))]\n",
    "        dp[0][nums[0] % 3] = nums[0]\n",
    "        for i in range(1, len(nums)):\n",
    "            for j in range(3):\n",
    "                c = nums[i] % 3\n",
    "                if dp[i - 1][j - c] or not j - c:\n",
    "                    dp[i][j] = max(nums[i] + dp[i - 1][j - c], dp[i - 1][j])\n",
    "                else:\n",
    "                    dp[i][j] = dp[i - 1][j]\n",
    "        return dp[-1][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy\n",
    "\n",
    "class Solution:\n",
    "    def maxSumDivThree(self, nums: List[int]) -> int:\n",
    "        dp = [[0 for _ in range(3)] for _ in range(len(nums))]\n",
    "        dp[0][nums[0] % 3] = nums[0]\n",
    "        for i in range(1, len(nums)):\n",
    "            for j in range(3):\n",
    "                c = nums[i] % 3\n",
    "                if dp[i - 1][j - c] or not j - c:\n",
    "                    dp[i][j] = max(nums[i] + dp[i - 1][j - c], dp[i - 1][j])\n",
    "                else:\n",
    "                    dp[i][j] = dp[i - 1][j]\n",
    "        return dp[-1][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumDivThree(self, nums: List[int]) -> int:\n",
    "        lst1, lst2, ans = [], [], 0\n",
    "        for n in nums:\n",
    "            n_ = n % 3\n",
    "            if   n_ == 1: lst1.append(n)\n",
    "            elif n_ == 2: lst2.append(n)\n",
    "            else        : ans += n\n",
    "        lst1.sort(reverse = True)\n",
    "        lst2.sort(reverse = True)\n",
    "        l1, l2 = len(lst1), len(lst2)\n",
    "        if l1 < l2: l1, l2, lst1, lst2 = l2, l1, lst2, lst1\n",
    "        #print(lst1, lst2, l1, l2, ans)        \n",
    "        @cache\n",
    "        def dfs(l):\n",
    "            if l == l2: return sum(lst1[l : l1 - (l1 - l) % 3])\n",
    "            return max(sum(lst1[l : l1 - (l1 - l) % 3]) + sum(lst2[l : l2 - (l2 - l) % 3]), lst1[l] + lst2[l] + dfs(l + 1))\n",
    "        return ans + dfs(0)\n",
    "        '''\n",
    "        l1, l2 = len(lst1), len(lst2)\n",
    "        if l1 < l2: l1, l2, lst1, lst2 = l2, l1, lst2, lst1\n",
    "        print(lst1, lst2, l1, l2, ans)        \n",
    "        print(sum(lst1[: l1 - l1 % 3]) + sum(lst2[: l2 - l2 % 3]), sum(x + y for x, y in zip(lst1, lst2)) + sum(lst1[l2:][: l1 - l2 - (l1 - l2) % 3]) )\n",
    "        return ans + max(sum(lst1[: l1 - l1 % 3]) + sum(lst2[: l2 - l2 % 3]), sum(x + y for x, y in zip(lst1, lst2)) + sum(lst1[l2:][: l1 - l2 - (l1 - l2) % 3])) \n",
    "        '''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumDivThree(self, nums: List[int]) -> int:\n",
    "        if len(nums)==0: return 0\n",
    "        self.nums = nums\n",
    "        return self.dp_runner(idx=0)[0]\n",
    "\n",
    "    def dp_runner(self, idx: int):\n",
    "        if idx == len(self.nums):\n",
    "            return 0, 0, 0\n",
    "        max_0, max_1, max_2 = self.dp_runner(idx+1)\n",
    "        cur_num = self.nums[idx]\n",
    "        if cur_num < 0:\n",
    "            return max_0, max_1, max_2\n",
    "        res = cur_num % 3\n",
    "        if res == 0:\n",
    "            return max_0 + cur_num, max_1 + cur_num if max_1 !=0 else 0, max_2 + cur_num if max_2 !=0 else 0\n",
    "        elif res == 1:\n",
    "            return max(max_0, max_2 + cur_num) if max_2 !=0 else 0, max(max_1, max_0+cur_num), max(max_2, max_1+cur_num) if max_1 !=0 else max_2\n",
    "        else:\n",
    "            return max(max_0, max_1 + cur_num) if max_1 !=0 else max_0, max(max_1, max_2+cur_num) if max_2 !=0 else max_1, max(max_2, max_0+cur_num)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumDivThree(self, nums: List[int]) -> int:\n",
    "        state = self.dfs(nums,len(nums)-1,{})\n",
    "        return state[0]\n",
    "\n",
    "    def dfs(self,nums,x,memo):\n",
    "        \n",
    "        if x == 0:\n",
    "            state = [0,0,0]\n",
    "            if nums[x]%3==0:\n",
    "                state[0] = nums[x]\n",
    "            if nums[x]%3==1:\n",
    "                state[1] = nums[x]\n",
    "            if nums[x]%3==2:\n",
    "                state[2] = nums[x]\n",
    "            \n",
    "            return state\n",
    "\n",
    "        if x in memo:\n",
    "            return memo[x]\n",
    "\n",
    "        state = self.dfs(nums,x-1,memo)\n",
    "        new_state = [state[0]+nums[x],state[1]+nums[x],state[2]+nums[x]]\n",
    "        \n",
    "        for i in range(len(state)):\n",
    "\n",
    "            if new_state[i] % 3 == 0:\n",
    "                state[0] = max(new_state[i],state[0])\n",
    "\n",
    "            if new_state[i] % 3 == 1:\n",
    "                state[1] = max(new_state[i],state[1])\n",
    "\n",
    "            if new_state[i] % 3 == 2:\n",
    "                state[2] = max(new_state[i],state[2])\n",
    "        \n",
    "        memo[x] = state\n",
    "       \n",
    "        return state\n",
    "\n",
    "       \n",
    "\n",
    "         \n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumDivThree(self, nums: List[int]) -> int:\n",
    "        global memo \n",
    "        global arr \n",
    "        arr = nums \n",
    "        # state dp[i][mod]: maximum sum of nums[0..i] with mod ,mod = 0, 1,2\n",
    "        n = len(nums)\n",
    "        memo = [[-1]*3 for _ in range(n)]\n",
    "        res = dp(n-1,0)\n",
    "        # print(memo)\n",
    "        if res == -float('inf'):\n",
    "            return 0 \n",
    "        return res \n",
    "\n",
    "memo = []\n",
    "arr = []\n",
    "def dp(i: int, m: int ) -> int:\n",
    "    global memo \n",
    "    global arr \n",
    "    # print(i,m)\n",
    "    if memo[i][m] != -1:\n",
    "        return memo[i][m]\n",
    "\n",
    "    # base cases \n",
    "    if i == 0:\n",
    "        if arr[0]%3 == m:\n",
    "            memo[i][m] = arr[0] \n",
    "        else:\n",
    "            memo[i][m] = 0\n",
    "        return memo[i][m]\n",
    "    # state transition \n",
    "    # dp(i,m) = dp(i-1,m-curMod) + arr[i]\n",
    "    # res = 0 \n",
    "    curMod = arr[i]%3 \n",
    "    prevMod = 0 \n",
    "\n",
    "    res = dp(i-1,m)\n",
    "    # try 3 cases  \n",
    "    \n",
    "    # res = max(dp(i-1,m),dp(i-1, (3+m-curMod)%3) + arr[i])\n",
    "    if curMod == m:\n",
    "        # choose this the number only\n",
    "        res = max(res,arr[i])\n",
    "    subproblem =  dp(i-1,(3+m-curMod)%3)\n",
    "    if subproblem !=0:\n",
    "        res = max(res,subproblem + arr[i])\n",
    "    \n",
    "    # res = max(dp(i-1,m), dp(i-1,(3+m-curMod)%3) + arr[i])\n",
    "    # res = max(res,0)\n",
    "\n",
    "    # save result \n",
    "    memo[i][m] = res \n",
    "    return memo[i][m]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumDivThree(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        memo = [[-1] * 3 for _ in range(n)]\n",
    "        # 从0到前i个数字mod为j的最大和\n",
    "        def dfs(i, j):\n",
    "            if memo[i][j] != -1:\n",
    "                return memo[i][j]\n",
    "            if i < 0:\n",
    "                res = 0 if j == 0 else -inf\n",
    "            else:\n",
    "                res = max(dfs(i - 1, j), dfs(i - 1, (j + nums[i]) % 3) + nums[i])\n",
    "            memo[i][j] = res\n",
    "            return memo[i][j]        \n",
    "        return dfs(n - 1, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    @lru_cache(maxsize=64)\n",
    "    def dp(self,i,rem):\n",
    "        if i==-1:\n",
    "            return -0x7fffffff if rem!=0 else 0\n",
    "        return max(self.dp(i-1,rem),self.dp(i-1,(rem-self.nums[i])%3)+self.nums[i])\n",
    "\n",
    "    def maxSumDivThree(self, nums: List[int]) -> int:\n",
    "        self.nums=nums\n",
    "        n=len(nums)\n",
    "        return self.dp(n-1,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumDivThree(self, nums: List[int]) -> int:\n",
    "        sums = list(accumulate(nums))\n",
    "        ans = 0\n",
    "        def dfs(i, s):\n",
    "            nonlocal ans\n",
    "            if i < 0: \n",
    "                # 如果最后能被3整除取最大值\n",
    "                if s % 3 == 0:\n",
    "                    ans = max(ans, s)\n",
    "                return\n",
    "            if ans > s + sums[i]:\n",
    "                return\n",
    "            dfs(i - 1, s + nums[i]) \n",
    "            dfs(i - 1, s) \n",
    "        dfs(len(nums) - 1, 0)\n",
    "        return ans\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumDivThree(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        dp={}\n",
    "        def helper(idx,remainder,dp):\n",
    "            if idx<0:\n",
    "                if not remainder:\n",
    "                    return 0\n",
    "                else:\n",
    "                    return -float('inf')\n",
    "            if (idx,remainder) in dp:\n",
    "                return dp[(idx,remainder)]\n",
    "            p1=helper(idx-1,(remainder-(nums[idx]%3))%3,dp)+nums[idx]\n",
    "            p2=helper(idx-1,remainder,dp)\n",
    "            dp[(idx,remainder)]=max(p1,p2)\n",
    "            return dp[(idx,remainder)]\n",
    "        return max(0,helper(n-1,0,dp))\n",
    "        # print(dp)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumDivThree(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        nums_len = len(nums)\n",
    "        pre_sum = [0] * (nums_len + 1)\n",
    "        for i in range(1, nums_len + 1):\n",
    "            pre_sum[i] = pre_sum[i - 1] + nums[i - 1]\n",
    "        # @cache\n",
    "        def dfs(i, the_sum):\n",
    "            if i < 0:\n",
    "                if  the_sum % 3==0:\n",
    "                    return the_sum\n",
    "                return 0\n",
    "            t = 0\n",
    "            # the_sum += nums[i]\n",
    "            if the_sum % 3==0:\n",
    "                t = the_sum\n",
    "            for j in range(i, -1, -1):\n",
    "                if pre_sum[j]+ the_sum+nums[j]< t:\n",
    "                    return t\n",
    "                t = max(t, dfs(j - 1, the_sum+nums[j]))\n",
    "            # print(t)\n",
    "            return t\n",
    "        ans = dfs(nums_len - 1, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumDivThree(self, nums: List[int]) -> int:\n",
    "        @lru_cache\n",
    "        def dfs(i, j):\n",
    "            if i < 0:\n",
    "                if not j:\n",
    "                    return 0\n",
    "                else:\n",
    "                    return -float('inf')\n",
    "            \n",
    "            return max(dfs(i-1, j), dfs(i-1, (j+nums[i])%3)+nums[i])\n",
    "        \n",
    "        return dfs(len(nums)-1, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumDivThree(self, nums: List[int]) -> int:\n",
    "        @cache\n",
    "        def dp(pos):\n",
    "            if pos == len(nums): return [0, -inf, -inf]\n",
    "            r = dp(pos + 1)\n",
    "            i = nums[pos] % 3\n",
    "            x = nums[pos]\n",
    "            if i == 0:\n",
    "                r[0], r[1], r[2] = r[0] + x, r[1] + x, r[2] + x\n",
    "            elif i == 1:\n",
    "                r[0], r[1], r[2] = max(r[0], r[2] + x), max(r[1], r[0] + x), max(r[2], r[1] + x)\n",
    "            elif i == 2:\n",
    "                r[0], r[1], r[2] = max(r[0], r[1] + x), max(r[1], r[2] + x), max(r[2], r[0] + x)\n",
    "            return r\n",
    "        return dp(0)[0]\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def maxSumDivThree(self, nums: List[int]) -> int:\n",
    "#         state = [0, float('-inf'), float('-inf')]\n",
    "\n",
    "#         for num in nums:\n",
    "#             temp = [0] * 3\n",
    "#             for i in range(3):\n",
    "#                 temp[(i + num) % 3] = max(state[(i + num) % 3], state[i] + num)\n",
    "#             state = temp\n",
    "\n",
    "#         return state[0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumDivThree(self, nums: List[int]) -> int:\n",
    "        from functools import lru_cache\n",
    "        n = len(nums)\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def recur(i, mod):\n",
    "            if i == n:\n",
    "                return 0 if mod == 0 else None\n",
    "            return max((r + j for r, j in zip((recur(i + 1, mod), recur(i + 1, (nums[i] + mod) % 3)), (0, nums[i])) if\n",
    "                        r is not None), default=None)\n",
    "\n",
    "        return recur(0,0) if recur(0,0) is not None else 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def maxSumDivThree(self, nums: List[int]) -> int:\n",
    "        total = sum(nums)\n",
    "        mod = total %3\n",
    " \n",
    "        @lru_cache(None)\n",
    "        def solve(i,mod):\n",
    "            if mod == 0:\n",
    "                return sum(nums[i:])\n",
    "                \n",
    "            if i == len(nums):\n",
    "                return -float('inf')\n",
    "            return max(nums[i]+solve(i+1,mod),solve(i+1,(mod-nums[i]%3)%3 ))\n",
    "        result = solve(0,mod)\n",
    "        if result == -float('inf'):\n",
    "            return 0\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumDivThree(self, nums: List[int]) -> int:\n",
    "        ans = sum([num for num in nums if num % 3 == 0])\n",
    "        nums = [num for num in nums if num % 3 != 0]\n",
    "        @cache\n",
    "        def dfs(i, d):\n",
    "            if i < 0:\n",
    "                if d != 0: return -inf\n",
    "                return 0\n",
    "            return max(dfs(i-1, (d+nums[i]) % 3)+nums[i], dfs(i-1, d))\n",
    "        return ans + dfs(len(nums)-1, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import functools\n",
    "class Solution:\n",
    "    def maxSumDivThree(self, nums: List[int]) -> int:\n",
    "        #能被三整除的元素最大和\n",
    "        #整数数组都是正数\n",
    "        s = sum(nums)\n",
    "        if s%3 == 0:\n",
    "            return s\n",
    "        n = len(nums)\n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(i,j):\n",
    "            if i<0:#递归边界：dfs(−1,0)=0,dfs(−1,1)=−∞,dfs(−1,2)=−∞\n",
    "                if j:\n",
    "                    return -math.inf\n",
    "                else:\n",
    "                    return 0\n",
    "                    # (s+x)mod3=j，即 s mod 3=(j−x) mod 3 \n",
    "            return max(dfs(i-1,j),dfs(i-1, (j+nums[i])%3)+nums[i])#第一个代表不选,j代表0，1，2\n",
    "            # dfs(i,j)=max(dfs(i−1,j),dfs(i−1,(j−x)mod3)+x)#为了防止j-x<0\n",
    "\n",
    "        \n",
    "        return dfs(n-1, 0)\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumDivThree(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        nums_len = len(nums)\n",
    "        pre_sum = [0] * (nums_len + 1)\n",
    "        for i in range(1, nums_len + 1):\n",
    "            pre_sum[i] = pre_sum[i - 1] + nums[i - 1]\n",
    "        @cache\n",
    "        def dfs(i, the_sum):\n",
    "            if i < 0:\n",
    "                if  the_sum % 3==0:\n",
    "                    return the_sum\n",
    "                return 0\n",
    "            t = 0\n",
    "            # the_sum += nums[i]\n",
    "            if the_sum % 3==0:\n",
    "                t = the_sum\n",
    "            for j in range(i, -1, -1):\n",
    "                if pre_sum[j]+ the_sum+nums[j]< t:\n",
    "                    return t\n",
    "                t = max(t, dfs(j - 1, the_sum+nums[j]))\n",
    "            # print(t)\n",
    "            return t\n",
    "        ans = dfs(nums_len - 1, 0)\n",
    "        return ans\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumDivThree(self, nums: List[int]) -> int:\n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            if i<0:\n",
    "                return -inf if j else 0\n",
    "            return max(dfs(i - 1, j), dfs(i - 1, (j + nums[i]) % 3) + nums[i])\n",
    "        return dfs(len(nums)-1,0)      "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
